// Copyright 2012 Jay Young. All Rights Reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//      http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS-IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

/**
 * @fileoverview
 *
 * Provides a linked hash map data structure usable as an LRU cache.
 */


var logger = require('ringo/logging').getLogger('Cache');



/**
 * An entry in the map has a "previous" pointer, a "next" pointer, and a "value"
 * pointer.  "previous", "next", or both may be null if at the beginning and/or
 * end of the linked list.
 *
 * @typedef {{previous: ?Entry, next: ?Entry, value: *}}
 */
var Entry;



/**
 * An implementation of an LRU cache.
 *
 * @param {number} capacity The allowable capacity for the map.
 * @constructor
 */
var Cache = exports.Cache = function(capacity) {
  /**
   * @type {number}
   * @private
   */
  this.capacity_ = capacity;

  /**
   * @type {number}
   * @private
   */
  this.size_ = 0;

  /**
   * The head of the linked list.
   *
   * @type {?Entry}
   * @private
   */
  this.head_ = null;

  /**
   * The tail end of the linked list.
   *
   * @type {?Entry}
   * @private
   */
  this.tail_ = null;

  /**
   * Use a prototype-less Object as the map from key to value.
   *
   * @type {Object.<string, Entry>}
   * @private
   */
  this.map_ = Object.create(null);
  
  /**
   * A counter of gets and hits for keys.
   *
   * @type {Object.<string, {{hits: number, gets: number}}>}
   * @private
   */
  this.gets_ = Object.create(null);
};


/**
 * Set a value into the map.  If it is already present, it will be moved
 * to the front of the list.
 *
 * @param {string} k The key to be mapped to the value.
 * @param {*} v The value to be stored in the map.
 */
Cache.prototype.set = function(k, v) {
  var head = this.head_,
      tail = this.tail_,
      entry = this.map_[k];

  if (! entry) {
    // Entry did not previously exist.  Add it to the front of the list.

    entry = {
      value: v,
      previous: null,
      next: null
    };
    
    this.touch(entry);

    this.size_ += 1;
    this.map_[k] = entry;

    if (this.size_ > this.capacity_) {
      var newTail = tail.previous;

      tail.previous = null;
      newTail.next = null;

      this.tail_ = newTail;

      this.size_ -= 1;
    }
  }
  else {
    entry.value = v;
    this.touch(entry);
  }
};


/**
 * Retrieves a value from the cache, moving it to the front of the list.
 *
 * @param {string} k The key to retrieve
 * @return {*} The mapped value, or null if the value is not in the map.
 */
Cache.prototype.get = function(k, v) {
  var gets = this.gets_;
  
  // If this key hasn't been gotten before, add it to the hit counter.
  if (! (k in gets)) {
    gets[k] = {hits: 0, gets: 0};
  }
  
  ++gets[k].gets;
  if (k in this.map_) {
    
    var entry = this.map_[k];
    this.touch(entry);

    ++gets[k].hits;
    return entry.value;
  }
  else {
    return null;
  }
};


/**
 * Moves an entry to the front of the list.  This could be a new entry or
 * one that is already in the list somewhere.
 *
 * @param {Entry} entry The entry to move.
 */
Cache.prototype.touch = function(entry) {
  var head = this.head_,
      tail = this.tail_;

  if (entry !== head) {
    // Move things around
    if (entry === tail) {
      tail = entry.previous;
      tail.next = null;
      this.tail_ = tail;
    }
    else {
      // It's not the head and it's not the tail, so it's either in the middle
      // or it's not in the list at all yet.  If it's in the list, it'll have
      // previous and next references that need to be updated.
      
      if (entry.previous && entry.next) {
        entry.previous.next = entry.next;
        entry.next.previous = entry.previous;
      }
    }

    if (head) {
      entry.next = head;
      head.previous = entry;  
    }
    else {
      // This is the first entry, so it's the head and tail.
      this.tail_ = entry;
    }

    entry.previous = null;
    this.head_ = entry;
  }
};


/**
 * Print the hits/gets details to logging.
 */
Cache.prototype.logHits = function() {
  var gets = this.gets_,
      keys = Object.keys(gets).sort(),

      totalGets = 0,
      totalHits = 0;

  for (var i = 0, len = keys.length; i < len; ++i) {
    var key = keys[i],
        keylog = gets[key],
        keyGets = keylog.gets,
        keyHits = keylog.hits,
        hitRate = Math.round(keyHits / keyGets * 10000) / 100;

    totalGets += keyGets;
    totalHits += keyHits;

    if (keyGets > 1) {
      logger.info('Key: ' + key + ' : Gets: ' + keyGets + ' : Hits: ' +
                  keyHits + ' : Hit Rate: ' + hitRate);
    }
  }

  logger.info('Total hits: ' + totalHits);
  logger.info('Total gets: ' + totalGets);
  logger.info('Total hit rate: ' + Math.round(totalHits / totalGets * 10000) /
              100 + '%');
  
  logger.info('Cache size: ' + this.size_);
};
